import java.util.Arrays;

public class 并查集Demo {

    public static void main(String[] args) {

        int[] nums = new int[] { 1, 2, 3, 4, 5 };
        UnionSetEntry unionSetEntry = new UnionSetEntry(nums.length + 1);

        Arrays.stream(unionSetEntry.getOriginArr(nums.length + 1)).forEach(System.out::print);
        System.out.println("");

        unionSetEntry.union(1, 2);
        unionSetEntry.union(4, 5);
        unionSetEntry.union(2, 3);

        Arrays.stream(unionSetEntry.getOriginArr(nums.length)).forEach(System.out::print);
        System.out.println("");

    }

    public static class UnionSetEntry {

        public int[] arr;

        public UnionSetEntry(int n) {
            arr = new int[n];
            for (int i = 0; i < n; i++) {

                arr[i] = i;
            }
        }

        // 查找
        public int find(int x) {

            if (x == arr[x])
                return x;
            return arr[x] = find(arr[x]);
        }

        public void union(int x, int y) {

            int xV = find(x);
            int yV = find(y);

            if (xV != yV) {

                arr[yV] = xV;
            }

        }

        public int[] getOriginArr(int n) {

            return arr == null ? new int[n] : arr;
        }
    }
}
